package 左哥算法.ch06二叉树;

import org.junit.Test;

import java.util.*;

public class Ch04几个练手题 {

    @Test
    public void test01(){
        TreeNode node = TreeNode.newLevelTree(new Integer[]{6, 2, 8, 0, 4, 7, 9, null, null, 3, 5});
        TreeNode node2 = node.left;
        TreeNode node3 = node.left.right.left;
        TreeNode node7 = node.right.left;
        System.out.println(lowestCommonAncestor(node, node3, node7));
        System.out.println(lowestCommonAncestor(node, node3, node2));
        System.out.println(lowestCommonAncestor2(node, node.left,node.right));
        System.out.println(lowestCommonAncestor2(node, node3, node7));
        System.out.println(lowestCommonAncestor2(node, node3, node2));
    }

    /**
     * ch01：二叉搜索树的最近公共祖先
     *思路1哈希表方式：
     *  1.首先通过遍历将每个节点的父节点存入hashMap中
     *  2.再通过这个hashMap找到节点a到根节点的路径，将路径放入Set中
     *  3.通过hashMap对节点b，进行从b到根节点的遍历，途中如果遍历到a路径上（set上）的节点，则返回第一个公共节点
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
        if (p==null||q==null){
            return p!=null?p:q;
        }
        Map<TreeNode,TreeNode> map = new HashMap<>();
        Set<TreeNode> set=new HashSet<>();
        map.put(root,null);
        putMap(root,map);
        TreeNode curr=p;
        while (curr!=null){
            set.add(curr);
            curr=map.get(curr);
        }
        curr=q;
        while (curr!=null){
            if (set.contains(curr)){
                return curr;
            }
            curr=map.get(curr);
        }
        return null;
    }

    /**
     * 将每个节点与其父节点放入map中（不含头）
     */
    public void putMap(TreeNode node, Map<TreeNode,TreeNode> map){
        if (node==null){
            return;
        }
        if (node.left!=null){
            map.put(node.left,node);
        }
        if (node.right!=null){
            map.put(node.right,node);
        }
        putMap(node.left,map);
        putMap(node.right,map);
    }

    /**
     *思路2递归：
     *  1.如果当前节点（根节点）是a或b中的一个，则另一个节点在当当前节点的子树上，所以当前节点是最近公共祖先
     *  2.如果当前节点不是a或b其中一个，则从左右子树中找a或b的父节点（并不一定是公共的）
     *  如果其中一个父节点在我的左树上，一个父节点在我的右树上，则我为a和b的公共父节点
     *  如果a和b在同一侧，则返回在该侧找到的公共父节点
     */
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q){
        if (root==null){
            return null;
        }
        if (root==p||root==q){
            return root;
        }
        TreeNode l = lowestCommonAncestor2(root.left, p, q);
        TreeNode r = lowestCommonAncestor2(root.right, p, q);
        if (l!=null&&r!=null){
            return root;
        }
        return l!=null?l:r;
    }


    /**
     * ch02：中序遍历的后继节点变体
     */
    @Test
    public void testLaterNode(){
        TreeNode2 root = TreeNode2.newLevelTree(new Integer[]{6, 2, 8, 0, 4, 7, 9, null, null, 3, 5});
        TreeNode2 node=root.left;
        System.out.println(laterNode(node));

        TreeNode2 node2=root.left.right.right;
        System.out.println(laterNode(node2));

        TreeNode2 node3=root.right.right;
        System.out.println(laterNode(node3));
    }
    /**
     * ch02：中序遍历的后继节点
     * 假设给节点一个parent属性，用于指向父节点
     * 请你用时间复杂度小于O(n)的算法找出它的后继节点
     *      思路：
     *          a如果存在右子树：后继节点为右子树最左节点
     *          b当前节不存在右子树：
     *              b.1当前节点为父节点的左孩子：后继节点是父节点
     *              b.2当前节点为右孩子：
     *                  1.将父节点变为当前节点
     *                  2.判断是否属于b.1
     *                  3.不符合则继续重复b.2
     */
    public TreeNode2 laterNode(TreeNode2 currNode){
        if (currNode==null){
            return null;
        }
        //存在右子树
        if (currNode.right!=null){
            currNode=currNode.right;
            while (currNode.left!=null){
                currNode=currNode.left;
            }
            return currNode;
        }
        while (currNode.parent!=null){
            if (currNode.parent.left==currNode){    //当前节点为左节点
                return currNode.parent;
            }
            currNode=currNode.parent;   //将父节点变为当前节点
        }
        return null;
    }

    @Test
    public void buildPreorderTest(){
        String inorder="4251630879";
        String postorder="4526318970";
        String preorder = buildPreorder(inorder, postorder, 0, 0, postorder.length());
        System.out.println(preorder);
    }

    /**
     * Ch03：已知二叉树的中序和后序，求前序
     * @param inorder：中序
     * @param postorder：后序
     * @param inorderStart：中序的起始位置
     * @param postorderStart：后序的起始位置
     * @param len：树的长度
     * 思路：
     *      后序遍历的最后一个节点一定是根节点，在中序中可以通过该根节点找出左子树和右子树。再找出左树和右树的根节点，以此往复
     */
    public String buildPreorder(String inorder,String postorder,int inorderStart,int postorderStart,int len){
        if (len<1){
            return "";
        }
        char root=postorder.charAt(postorderStart+len-1);
        if (len==1){
            return root+"";
        }

        int rootIndex=inorderStart;
        for (int i = inorderStart; i < inorder.length(); i++) {
            if (root==inorder.charAt(i)){
                rootIndex=i;
                break;
            }
        }
        //左子树，左子树中序和后序起点都是原先的起点，改变的只有树的长度。左树长度=根-起点
        String left = buildPreorder(inorder, postorder, inorderStart, postorderStart, rootIndex - inorderStart);
        //右子树，中序的起点为根节点的下一个（左中右），后序的起点为，原先的起点加上左子树的长度（左右中），右树长度=总长度-左树长度-1
        String right = buildPreorder(inorder, postorder, rootIndex + 1, postorderStart+(rootIndex-inorderStart), len -(rootIndex-inorderStart)-1);
        return root+left+right;
    }
}